/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/smallest-subset
   @Language: C++
   @Datetime: 19-06-25 10:17
   */

class Solution {
public:
	/**
	 * @param arr:  an array of non-negative integers
	 * @return: minimum number of elements
	 */
	int minElements(vector<int> &arr) {
		// write your code here
		sort(arr.begin(),arr.end());
		int sum=0, part=0;
		for(int i=arr.size(); i--; sum+=arr[i]);
		for(int i=arr.size(); i--;){
			part+=arr[i];
			if(part>sum/2.0) return arr.size()-i;
		}
		return 0;
	}
};
